home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / werkzeuge.me < prev   
Text File  |  1992-09-25  |  50KB  |  1,467 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .de []        \" start to display collected references
  380. .uh Literatur
  381. ..
  382. .hc ~
  383. .ds ], , 
  384. .EQ
  385. gsize 12
  386. delim $$
  387. .EN
  388. .b " "
  389. .sp 1c
  390. .ta 9c
  391. .ft R
  392. .sz 12
  393. \l'17.1c'
  394. .nf
  395.  
  396.  
  397.     Werkzeuge f\*ur den
  398.     \*Ubersetzerbau
  399.  
  400.     J. Grosch
  401.     H. Emmelmann
  402.  
  403. \l'17.1c'
  404. .sp 12.5c
  405. \l'17.1c'
  406. .ft H
  407. .nf
  408.     GESELLSCHAFT F\*UR MATHEMATIK
  409.     UND DATENVERARBEITUNG MBH
  410.  
  411.     FORSCHUNGSSTELLE F\*UR
  412.     PROGRAMMSTRUKTUREN
  413.     AN DER UNIVERSIT\*AT KARLSRUHE
  414. .r
  415. \l'17.1c'
  416. .bp
  417. .oh '''%'
  418. .eh '''%'
  419. .ce 99
  420. .sz 20
  421. .b " "
  422. .sp 2
  423. Project
  424. .sp
  425. .b "Compiler Generation"
  426. .sp
  427. .sz 12
  428. \l'15c'
  429. .sp
  430. .sz 16
  431. .b "Werkzeuge f\*ur den \*Ubersetzerbau"
  432. .sp 2
  433. Josef Grosch
  434. Helmut Emmelmann
  435. .sp 2
  436. .sz 14
  437. Feb. 7, 1990
  438. .sp
  439. .sz 12
  440. \l'15c'
  441. .sp 2
  442. Report No. 21
  443. .sp 2
  444. Copyright \(co 1990 GMD
  445. .sp 2
  446. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  447. Forschungsstelle an der Universit\*at Karlsruhe
  448. Vincenz-Prie\*snitz-Str. 1
  449. D-7500 Karlsruhe
  450. .ce 0
  451. .fi
  452. .bp 1
  453. .ce 99
  454. .b "Werkzeuge f\*ur den \*Ubersetzerbau"
  455. .sp
  456. J. Grosch, H. Emmelmann
  457. GMD Forschungsstelle an der Universit\*at Karlsruhe
  458. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  459. .\" Tel: +721-6622-26
  460. .\" E-Mail: grosch@karlsruhe.gmd.de, emmel@karlsruhe.gmd.de
  461. .ce 0
  462. .sp
  463. .uh \*Ubersicht
  464. .pp
  465. Mit \*Ubersetzerbau-Werkzeugen lassen sich \*Ubersetzer f\*ur Programmiersprachen weitgehend
  466. automatisch generieren. Wir stellen einen Werkzeugkasten vor, welcher die Konstruktion
  467. nahezu aller Phasen eines \*Ubersetzers unterst\*utzt. Die Entwurfsziele f\*ur diesen
  468. Werkzeugkasten waren praktische Brauchbarkeit, deutlich reduzierter Erstellungsaufwand f\*ur
  469. \*Ubersetzer und hohe Qualit\*at der generierten \*Ubersetzer. Besonders hinsichtlich
  470. Effizienz sollten die Werkzeuge konkurrenzf\*ahig zur Programmierung von Hand sein.
  471. .\" pp
  472. Zur Zeit k\*onnen mit den Werkzeugen \*Ubersetzermodule in den Zielsprachen C und Modula-2
  473. erzeugt werden. Erste rea~listische Anwendungen demonstrieren die ausgezeichnete
  474. Leistungsf\*ahigkeit der Werkzeuge und zeigen, da\*s die Werkzeuge die Konstruktion von
  475. \*Ubersetzern mit Produktionsqualit\*at erlauben.
  476. .sh 1 "Aufbau eines \*Ubersetzers"
  477. .pp
  478. Ein wichtiges Hilfsmittel zur Programmierung eines Computers ist ein \*Ubersetzer (compiler).
  479. Ein \*Ubersetzer ist ein Programm, welches ein in einer Programmiersprache geschriebenes
  480. Programm in eine Maschinensprache \*ubersetzt. Die Hardware versteht genaugenommen nur
  481. aus Nullen und Einsen zusammengesetzte Maschinensprach-Programme. Um einem Computer auch eine
  482. f\*ur den menschlichen Programmierer besser geeignete h\*ohere Programmiersprache
  483. verst\*andlich zu machen, ist eine \*Ubersetzung n\*otig.
  484. .pp
  485. Die Konstruktion eines \*Ubersetzers ist eine anspruchsvolle und  
  486. aufwendige Aufgabe. Der Bedarf an \*Ubersetzern ist relativ gro\*s, da
  487. f\*ur jede Programmiersprache und jeden Computer ein eigener \*Ubersetzer notwendig ist.
  488. Es lohnt sich daher, nach Methoden zu suchen die Erstellung von Compilern zu vereinfachen.
  489. Doch bevor wir zu unserem eigentlichen Thema kommen, n\*amlich
  490. der automatischen Generierung von \*Ubersetzern mit \*Ubersetzerbau-Werkzeugen, m\*ochten wir
  491. kurz den Aufbau und die prinzipielle Funktionsweise eines \*Ubersetzers erl\*autern.
  492. Die rechte Spalte in Abb. 1 zeigt die Phasen bzw. Module eines \*Ubersetzers.
  493. .pp
  494. Die lexikalische Analyse liest das Quellprogramm zeichenweise. Sie fa\*st die Zeichenfolgen
  495. f\*ur Bezeichner, Zahlen und Schl\*usselw\*orter zu Grundsymbolen zusammen und \*uberliest
  496. Zwischenr\*aume und Kommentare.
  497. .pp
  498. Die syntaktische Analyse hat als Eingabe eine Folge von Grundsymbolen. Sie \*uberpr\*uft das
  499. Quellprogramm auf syntaktische Fehler und rekonstruiert die Struktur des Programms, d. h. sie
  500. erkennt den Aufbau der Ausdr\*ucke und Anweisungen sowie deren Zusammenhang. Diese Struktur
  501. wird oft in Form eines Syntaxbaums gespeichert.
  502. .pp
  503. Die semantische Analyse \*uberpr\*uft die Kontextbedingungen bzw. die Regeln der statischen
  504. Semantik und berechnet f\*ur die Codegenerierung n\*otige Eigenschaften. Ein Beispiel f\*ur
  505. eine Kontextbedingung ist die Vorschrift, da\*s alle Variablen deklariert sein m\*ussen.
  506. Zur statischen Semantik z\*ahlen die Analyse der G\*ultigkeitsbereiche, die Namensanalyse, d.
  507. h. die Feststellung der zu einem Bezeichner geh\*orenden Deklaration, und die
  508. Typ\*uberpr\*ufung.
  509. .pp
  510. Zur Vereinfachung der gesamten \*Ubersetzungsaufgabe wird diese h\*aufig in zwei Schritte
  511. unterteilt. Der Syntaxbaum wird zun\*achst von einer Transformationsphase in eine
  512. Zwischensprache umgewandelt. Diese Zwischensprache ist meist maschinenorientiert jedoch
  513. noch maschinenunabh\*angig. Das niedrige Niveau der Zwischensprache erleichtert dem
  514. Codegenerator die Erzeugung der Maschinensprache.
  515. .pp
  516. Zu den Aufgaben des Codegenerators z\*ahlen die Befehlsauswahl, d. h. die Abbildung der
  517. Zwischensprachanweisungen auf Maschinenbefehle, sowie die Speicher- und Registerzuteilung.
  518. Die Ausgabe ist schlie\*slich ein bin\*ar-codiertes Maschinenprogramm.
  519. .pp
  520. Der folgende Abschnitt beschreibt die Vorteile, die Entwurfsziele und den Inhalt des Werkzeugkastens.
  521. Abschnitt 3 stellt die gemeinsamen Eigenschaften der Werkzeuge dar.
  522. Im Abschnitt 4 wird das von uns bevorzugte \*Ubersetzermodell beschrieben.
  523. Der Abschnitt 5 enth\*alt eine kurze Darstellung der einzelnen Werkzeuge.
  524. Ab~schnitt 6 berichtet von den Erfahrungen des Einsatzes der Werkzeuge in zwei realistischen Anwendungen.
  525. Abschnitt 7 enth\*alt eine Zusammenfassung und beschreibt weiterf\*uhrende Arbeiten.
  526. .sh 1 Werkzeugkasten
  527. .pp
  528. Die Erstellung eines \*Ubersetzers von Hand ist eine sehr anspruchsvolle  und
  529. aufwendige Aufgabe.
  530. Durch den Einsatz von \*Ubersetzerbau-Werkzeugen l\*a\*st sich dieser Aufwand re~du~zie~ren.
  531. Im folgenden stellen wir einen Werkzeugkasten zur \*Ubersetzer-Generierung vor,
  532. welcher f\*ur nahezu jede \*Ubersetzerphase Werkzeuge enth\*alt.
  533. Diese sind f\*ur den Einsatz in realistischen \*Ubersetzerprojekten konzipiert.
  534. .pp
  535. Im allgemeinen akzeptieren die Werkzeuge als Eingabe eine Spezifikation, die in einer
  536. werkzeug-spezifischen Sprache geschrieben ist. Sie produzieren als Ausgabe ein
  537. Programm-Modul in einer Zielsprache (C oder Modula-2). Deshalb kann ein Werkzeug als
  538. ge~ne~ri~sche L\*osung eines Teilproblems in einem \*Ubersetzer gesehen werden, wobei mit
  539. Hilfe einer Spezifikation eine konkrete L\*osung gewonnen wird.
  540. .pp
  541. Die Benutzung von Werkzeugen hat gegen\*uber der Programmierung von Hand mehrere Vorteile:
  542. Der zur Konstruktion eines \*Ubersetzers notwendige Aufwand wird wesentlich verringert. An
  543. Stelle eines Programms wird eine viel k\*urzere Spezifikation entwickelt. Die Werkzeuge
  544. k\*onnen eine Spezifikation in vielfacher Weise auf Konsistenz \*uberpr\*ufen. Das Schreiben
  545. automatisch pr\*ufbarer Spezifikationen verringert die Anzahl m\*oglicher Fehler und erh\*oht
  546. so die Zuverl\*assigkeit des resultierenden \*Ubersetzers.
  547. .pp
  548. Die wichtigsten Entwurfsziele f\*ur den Werkzeugkasten waren:
  549. .ip -
  550. praktische Brauchbarkeit f\*ur realistische Programmiersprachen
  551. .ip -
  552. automatische Generierung von \*Ubersetzern mit Produktionsqualit\*at
  553. .ip -
  554. wesentliche Steigerung der \*Ubersetzerbau-Produktivit\*at
  555. .ip -
  556. mit Handprogrammierung vergleichbare Qualit\*at der erzeugten \*Ubersetzer
  557. .pp
  558. Mit dieser Zielsetzung  sollte die praktische Einsatzf\*ahigkeit
  559. des Werkzeugkastens in rea~li~sti~schen \*Ubersetzerbauprojekten
  560. erreicht werden. Daher wurde auch die Konkurrenzf\*ahigkeit
  561. zur Handprogrammierung betont. Wir meinen, da\*s die hohe
  562. Produktivit\*at und Zuverl\*assigkeit nicht durch eine
  563. geringere Codequalit\*at oder Effizienz des resultierenden Compilers
  564. erkauft werden mu\*s.
  565. .pp
  566. Der Werkzeugkasten enth\*alt folgende Werkzeuge:
  567. .(b
  568. .ta 2c
  569. Rex    Generator f\*ur lexikalische Analysatoren
  570. Lalr    LALR(1) Zerteilergenerator
  571. Ell    LL(1) Zerteilergenerator
  572. Ast    Generator f\*ur abstrakte Syntaxb\*aume
  573. Ag    Generator f\*ur Attributauswerter
  574. Estra    Transformation abstrakter Syntaxb\*aume
  575. Beg    Generator f\*ur Codegeneratoren
  576. Reuse    Bibliothek wiederverwendbarer Module
  577. .)b
  578. .pp
  579. Alle Werkzeuge wurden urspr\*unglich in Modula-2 programmiert und laufen unter dem
  580. Betriebssystem UNIX. Unter Verwendung des Modula-2 nach C \*Ubersetzers
  581. .i Mtc
  582. \*([[Mar90\*(]] (siehe Abschnitt 6.1), konnte von den Programmen automatisch eine
  583. C-Version erstellt werden. Zur Zeit erzeugen die meisten Werkzeuge Module in den Zielsprachen
  584. C und Modula-2.
  585. .sh 1 "Gemeinsame Eigenschaften"
  586. .pp
  587. Unsere Entwurfsziele f\*uhrten zu einigen f\*ur alle Werkzeuge gemeinsamen
  588. Entwurfsentscheidungen. Nahezu jedes Werkzeug ben\*otigt eine Programmiersprache, mit der der
  589. Benutzer gewi\*se Aktionen, Bedingungen oder Berechnungen spezifizieren kann. Das trifft
  590. offensichtlich f\*ur Attributgrammatiken zu, aber auch der Codegenerator-Generator mu\*s
  591. Attribute und Bedingungen auswerten. Sogar die Zerteilergeneratoren brauchen eine solche
  592. Sprache zur Spezifikation semantischer Aktionen.
  593. .pp
  594. Wir entschieden uns daf\*ur direkt die Zielsprache (n\*amlich C oder Modula-2) zu verwenden.
  595. Deshalb k\*onnen Spezifikationen Abschnitte mit Zielsprachanweisungen enthalten. Abgesehen von
  596. geringf\*ugigen Ersetzungen wird dieser Text unver\*andert in die erzeugten Module kopiert.
  597. Der Nachteil dieser Methode ist, da\*s die in der Zielsprache geschriebenen Teile nicht
  598. vollst\*andig von den Werkzeugen \*uberpr\*uft werden k\*onnen. Zum Beispiel kann das
  599. Attri~but~gram~matik-Werkzeug nicht \*uberpr\*ufen, ob Attributberechnungen keine Seiteneffekte
  600. haben. Andererseits wird damit eine sehr gro\*se Flexibilit\*at erreicht, da die volle
  601. Ausdruckskraft der Zielsprache zur Verf\*ugung steht. Ebenso wird die praktische
  602. Brauchbarkeit drastisch erh\*oht, da die Einbeziehung anderer, eventuell handgeschriebener
  603. Komponenten leicht m\*oglich ist. Schlie\*slich f\*uhrt es zu einfachen Werkzeugen und
  604. einfachen Spezifikationssprachen.
  605. .pp
  606. Unsere Erfahrung mit fr\*uheren Werkzeugen zeigte, da\*s w\*ahrend der Konstruktion
  607. rea~li~sti~sche \*Ubersetzer eine Reihe kleiner Sonderprobleme auftritt, die nicht mit den
  608. Werkzeugen gel\*ost werden k\*onnen. Deswegen sind Schlupfl\*ocher n\*otig, also
  609. M\*oglichkeiten, die es dem Werkzeugbenutzer erlauben leicht handgeschriebene Teile
  610. einzuf\*ugen. Diese Schlupfl\*ocher tragen auch dazu bei die Werkzeuge einfach zu machen, da
  611. man nicht gezwungen ist, f\*ur jedes Problem sofort eine L\*osung bereitzustellen. Das
  612. Schlupfloch kann benutzt werden solange bis eine wirklich gute L\*osung gefunden wird, welche
  613. man in ein Werkzeug einbauen kann.
  614. .pp
  615. Die Werkzeuge sind gr\*o\*stenteils von einander unabh\*angig. Dies wird dadurch erzielt,
  616. da\*s keines der erzeugten Module eine festgelegte Ausgabe besitzt. Stattdessen wird diese
  617. Ausgabe mittels Anweisungen der Zielsprache spezifiziert und kann somit beliebig gew\*ahlt
  618. werden. Die Unabh\*angigkeit der Werkzeuge sorgt f\*ur gro\*se Freiheiten beim
  619. \*Ubersetzerentwurf. Eine Ausnahme bilden die Werkzeuge
  620. .i Ag
  621. und
  622. .i Estra ,
  623. denn sie basieren auf den mit
  624. .i Ast
  625. spezifizierten Syntaxb\*aumen. Deshalb h\*angen diese Werkzeuge von
  626. .i Ast
  627. ab, und alle drei Werkzeuge sind f\*ur \*Ubersetzer zugeschnitten, die einen attributierten
  628. abstrakten Syntaxbaum benutzen.
  629. .(z
  630. .PS
  631. linewid    = linewid * 1.2
  632. boxwid    = boxwid * 1.7
  633. boxht    = boxht * 1.2
  634. circlerad = circlerad * 1.2
  635. bh    = boxht * 1.7
  636. bw    = boxwid * 0.5
  637.  
  638.     right
  639.  
  640. S1:    box wid bw height bh invis
  641. SP:    box wid boxwid * 1.6 "regul\*are Ausdr\*ucke"
  642.     arrow
  643. T:    circle "rex"
  644.     arrow
  645. I1:    box "lexikalische" "Analyse"
  646.  
  647. S2:    box at S1 - (0, bh) wid bw height bh invis
  648. P:    box wid boxwid * 1.6 "konkrete Syntax" "(Grammatik)" "Abb.: konkret \(-> abstrakt"
  649.     arrow
  650.     circle "lalr" "ell"
  651.     arrow
  652. I2:    box "syntaktische" "Analyse"
  653.  
  654. S3:    box at S2 - (0, bh) wid bw height bh invis
  655.     box wid boxwid * 1.6 "abstrakte Syntax" "(Grammatik)"
  656.     arrow
  657.     circle "ast"
  658.     arrow
  659. I3:    box "Syntaxbaum"
  660.  
  661. S4:    box at S3 - (0, bh) wid bw height bh invis
  662.     box wid boxwid * 1.6 "Attribut-Grammatik"
  663.     arrow
  664.     circle "ag"
  665.     arrow
  666. I4:    box "semantische" "Analyse"
  667.  
  668. S5:    box at S4 - (0, bh) wid bw height bh invis
  669.     box wid boxwid * 1.6 "Abb.:" "abstrakt \(-> Zwischensprache"
  670.     arrow
  671.     circle "estra"
  672.     arrow
  673. I5:    box "Transformation"
  674.  
  675. S6:    box at S5 - (0, bh) wid bw height bh invis
  676.     box wid boxwid * 1.6 "Zwischensprache" "(Grammatik)"
  677.     arrow
  678.     circle "ast"
  679.     arrow
  680. I6:    box "Zwischensprache"
  681.  
  682. S7:    box at S6 - (0, bh) wid bw height bh invis
  683.     box wid boxwid * 1.6 "Abb.:" "Zwischensprache \(->" "Maschinensprache"
  684.     arrow
  685.     circle "beg"
  686.     arrow
  687. I7:    box "Codegenerator"
  688.  
  689.     box invis "Spezifikation" at SP + (0, bh)
  690.     box invis "Werkzeug" at T + (0, bh)
  691.     box invis "\*Ubersetzer-Modul" at I1 + (0, bh)
  692.  
  693.     line from I1.n up boxht * 0.9 <-
  694.     arrow from I1.s to I2.n
  695.     arrow from I2.s to I3.n
  696.     arrow from I3.s to I4.n <->
  697.     arc from I3.se to I5.ne at I4 -> cw
  698.     arrow from I5.s to I6.n
  699.     arrow from I6.s to I7.n
  700.     arrow from I7.s down boxht * 0.9
  701. .PE
  702. .sp 0.5
  703. .ce
  704. Abb. 1: \*Ubersetzer-Modell
  705. .)z
  706. .sh 1 "\*Ubersetzer-Modell"
  707. .pp
  708. Obwohl die Werkzeuge kein bestimmtes \*Ubersetzer-Modell erzwingen, m\*ochten wir das von uns
  709. bevorzugte Modell vorstellen. Wir meinen, da\*s dieses am besten von den Werkzeugen
  710. unterst\*utzt wird. Wir betrachten die semantische Analyse nach wie vor als den schwierigsten
  711. Teil eines \*Ubersetzers. Deshalb gehen wir f\*ur die semantische Analyse und die Erzeugung
  712. einer Zwischensprache von der abstrakten Syntax aus. Wir bauen den abstrakten Syntaxbaum
  713. explizit auf, welcher w\*ahrend der semantischen Analyse eventuell mit Attributen erg\*anzt
  714. wird. Neben der abstrakten Syntax, welche als erste, hohe Zwischensprache betrachtet werden
  715. kann, bevorzugen wir die Verwendung einer zweiten, niederen Zwischensprache als Schnittstelle
  716. zum Codegenerator. Dies bringt Vorteile in der Optimierung und der mustergesteuerten
  717. Codeauswahl mit sich.
  718. .pp
  719. Abbildung 1 zeigt das von uns bevorzugte \*Ubersetzermodell. Die rechte Spalte enth\*alt die
  720. wichtigsten Module eines \*Ubersetzers. Die linke Spalte zeigt die dazu notwendigen
  721. Spezifikationen. Die dazwischen liegenden Werkzeuge werden von den Spezifikationen gesteuert
  722. und erzeugen die einzelnen Module. Die Pfeile stellen den Datenflu\*s dar, teils zur
  723. Generierungszeit und teils zur \*Ubersetzungszeit.
  724. .\" .pp
  725. .\" Im Prinzip arbeitet das \*Ubersetzermodell folgenderma\*sen: Die lexikalische und
  726. .\" syntaktische Analyse lesen die Quelle, pr\*ufen die konkrete Syntax und bauen einen
  727. .\" abstrakten Syntaxbaum auf. Sie k\*onnen verschiedene Normalisierungen, Vereinfachungen und
  728. .\" Transformationen durchf\*uhren, um die abstrakte Syntax relativ einfach zu halten. Auf dem
  729. .\" abstrakten Syntaxbaum findet dann die semantische Analyse statt. M\*oglicherweise werden
  730. .\" Attribute zur Codeerzeugung berechnet. Danach wird der abstrakte Syntaxbaum in eine
  731. .\" niedere Zwischensprache transformiert. Diese ist Eingabe f\*ur den Codegenerator, welcher
  732. .\" schlie\*slich den Maschinencode erzeugt.
  733. .sh 1 "Die Werkzeuge"
  734. .pp
  735. Die folgenden Abschnitte stellen kurz die einzelnen Werkzeuge des Werkzeugkastens vor. Wir
  736. beschreiben nur die Eigenschaften der Werkzeuge. F\*ur weitere Einzelheiten, die
  737. Spezifikationstechniken oder f\*ur Beispiele sei der Leser auf die existierenden,
  738. werkzeug-spezifischen Dokumente verwiesen.
  739. .sh 2 Rex
  740. .pp
  741. .i Rex
  742. (\fIr\fPegular \fIex\fPpression tool) ist ein Generator f\*ur lexikalische Analysatoren
  743. \*([[Gro87a\*(],Gro88\*(],Gro89a\*(]].
  744. Seine Spezifikationen basieren auf regul\*aren Ausdr\*ucken und beliebigen
  745. semantischen Aktionen, die in einer der Zielsprachen C oder Modula-2 geschrieben werden.
  746. Immer wenn in der Eingabe des erzeugten lexikalischen Analysators eine einem regul\*aren
  747. Ausdruck entsprechende Zeichenkette erkannt wurde, werden die zugeh\*origem Aktionen
  748. ausgef\*uhrt. Falls zur eindeutigen Erkennung der Symbole der Kontext
  749. betrachtet werden mu\*s, so kann der rechte Kontext durch einen
  750. zus\*atzlichen regul\*aren Ausdruck spezifiziert werden, und der linke
  751. Kontext wird mit sogenannten Start-Zust\*anden behandelt.
  752. Falls mehrere regul\*are Ausdr\*ucke auf die aktuelle Eingabe zutreffen, so wird der Ausdruck
  753. mit der l\*angsten Zeichenkette bevorzugt. Falls es immer noch mehrere M\*oglichkeiten gibt,
  754. so wird der zuerst in der Spezifikation stehende Ausdruck gew\*ahlt.
  755. .pp
  756. Die erzeugten lexikalischen Analysatoren berechnen automatisch Zeile und Spalte in der Quelle
  757. f\*ur jedes erkannte Symbol und enthalten einen Mechanismus f\*ur Include-Dateien.
  758. Bezeichner und Schl\*usselw\*orter k\*onnen effizient in Gro\*s- oder
  759. Kleinbuchstaben normalisiert werden. Es gibt vordefinierte Regeln um Leerstellen,
  760. Tabulatoren und Zeilenwechsel zu \*uberlesen.
  761. Die ge~ne~rier~ten lexikalischen Analysatoren sind tabellengesteuerte, deterministische
  762. endliche Automaten. Die Tabellen werden mit der sogenannten Kammvektortechnik komprimiert
  763. \*([[ASU86\*(]].
  764. .pp
  765. Die herausragende Eigenschaft von \fIRex\fP ist seine Geschwindigkeit.
  766. Die lexikalischen Analysatoren verarbeiten nahezu 200.000 Zeilen pro Minute ohne Hashing von
  767. Bezeichnern und 150.000 Zeilen pro Minute mit Hashing. Dies ist die vierfache Geschwindigkeit
  768. gegen\*uber mit \fILex\fP\*([<\*([[Les75\*(]]\*(>] generierten lexikalischen Analysatoren. In typischen
  769. F\*allen besitzen mit \fIRex\fP ge~ne~rier~te Analysatoren ein Viertel der Gr\*o\*se derer von
  770. \fILex\fP. Normalerweise ben\*otigt
  771. \fIRex\fP nur 1/10 der Zeit von \fILex\fP zum Generieren eines lexikalischen Analysators.
  772. .sh 2 Lalr
  773. .pp
  774. .i Lalr
  775. ist ein LALR(1) Zerteiler-Generator der Grammatiken, die in 
  776. erweiterter BNF geschrieben sind, verarbeitet\*([<\*([[GrV88\*(],Gro88\*(]]\*(>].
  777. Die Grammatikregeln k\*onnen mit semantischen Aktionen versehen werden,
  778. die direkt in einer Zielsprache formuliert sind.
  779. Immer wenn der erzeugte Zerteiler eine Grammatikregel erkennt, wird die zugeh\*orige
  780. semantische Aktion ausgef\*uhrt.
  781. Der Generator stellt einen Mechanismus zur S-Attributierung zur Verf\*ugung,
  782. d. h. synthetisierte Attribute k\*onnen w\*ahrend der Zerteilung berechnet werden.
  783. .pp
  784. Im Falle von LR-Konflikten liefert \fILalr\fP nicht wie andere
  785. Generatoren nur Information \*uber aus Mengen von Situationen bestehende
  786. Zust\*ande, sondern druckt einen Ableitungsbaum, der wesentlich n\*utzlicher
  787. zur Analyse des Konflikts ist. Konflikte k\*onnen durch die Angabe von
  788. Priorit\*at und Assoziativit\*at f\*ur Operatoren und Produktionen gel\*ost
  789. werden. Die generierten Zerteiler beinhalten eine automatische
  790. Fehlerbehandlung mit Fehlermeldungen und -reparatur.
  791. Zur Fehlerbehandlung wird die vollst\*andige,
  792. r\*ucksetzungsfreie Methode von R\*ohrich
  793. \*([[R\*oh76\*(],R\*oh80\*(],R\*oh82\*(]]
  794. verwendet. Die Zerteiler sind
  795. tabellengesteuert und wie im Falle von \fIRex\fP werden die Tabellen mit der
  796. Kammvektortechnik komprimiert. Der Generator verwendet den in\*([<\*([[DeP82\*(]]\*(>]
  797. beschriebenen Algorithmus zur Berechnung der Vorschaumengen.
  798. .pp
  799. Mit \fILalr\fP erzeugte Zerteiler sind zwei bis drei mal schneller als mit \fIYacc\fP
  800. \*([[Joh75\*(]] erzeugte. Sie erreichen eine Geschwindigkeit von 580.000 Zeilen pro
  801. Minute ohne Ber\*ucksichtigung der lexikalischen Analyse. Die Gr\*o\*se der Zerteiler ist
  802. gegen\*uber \fIYacc\fP leicht erh\*oht, denn f\*ur die Geschwindigkeit mu\*s ein kleiner
  803. Preis bezahlt werden.
  804. .pp
  805. Die Eingabesprachen von
  806. .i Rex
  807. und
  808. .i Lalr
  809. sind hinsichtlich der Syntax gegen\*uber
  810. .i Lex
  811. und
  812. .i Yacc
  813. lesbarer gestaltet. Mit Hilfe zweier, hier nicht n\*aher beschriebener Pr\*aprozessoren
  814. k\*onnen
  815. .i Rex
  816. und
  817. .i Lalr
  818. auch Eingaben f\*ur
  819. .i Lex
  820. und
  821. .i Yacc
  822. verarbeiten. Dadurch sind unsere Werkzeuge in Bezug auf die Benutzerschnittstelle kompatibel
  823. mit den UNIX-Werkzeugen.
  824. .sh 2 Ell
  825. .pp
  826. .i Ell
  827. ist ein LL(1) Zerteiler-Generator, der die gleiche Spezifikationssprache wie
  828. \fILalr\fP verarbeitet, mit dem Unterschied, da\*s die Grammatiken die
  829. LL(1)-Eigenschaft besitzen m\*ussen
  830. \*([[GrV88\*(],Gro88\*(],Gro89b\*(]].
  831. W\*ahrend der Zerteilung kann eine
  832. L-Attributierung ausgewertet werden. Die erzeugten Zerteiler beinhalten
  833. eine automatische Fehlerbehandlung mit Fehlermeldungen und -reparatur wie
  834. \fILalr\fP. Die Zerteiler sind nach dem Verfahren des rekursiven Abstiegs
  835. implementiert und erzielen eine Geschwindigkeit von 900.000 Zeilen pro Minute.
  836. .sh 2 Ast
  837. .pp
  838. .i Ast
  839. ist ein Generator f\*ur abtrakte Syntaxb\*aume
  840. \*([[Gro89d\*(],Gro89e\*(]].
  841. Er generiert Programm-Module oder abstrakte Datentypen zur Bearbeitung attributierter
  842. B\*aume. Neben B\*aumen k\*onnen auch attributierte Graphen bearbeitet werden. Den Knoten
  843. dieser Datenstrukturen k\*onnen beliebig viele Attribute von beliebigem Typ zugeordnet
  844. werden. Die Spezifikationen f\*ur dieses Werkzeug basieren auf erweiterten Baum-Grammatiken.
  845. Sie k\*onnen als gemeinsame Notation sowohl f\*ur konkrete und abstrakte Syntax
  846. als auch f\*ur attributierte B\*aume und Graphen betrachtet werden. Ein Erweiterungsmechanismus
  847. stellt einfache Vererbung zur Verf\*ugung. Intern werden die B\*aume durch verzeigerte
  848. Verbunde gespeichert. Zahlreiche Operationen f\*ur B\*aume und Graphen k\*onnen auf
  849. Anforderung von
  850. .i Ast
  851. erzeugt werden: Sogenannte Knotenkonstruktoren kombinieren Aggregatschreibweise mit
  852. Speicherverwaltung. Lese- und Schreibeprozeduren \*ubertragen Graphen aus/in Dateien in
  853. lesbarem ASCII- oder internem Bin\*arformat. Die Reihenfolge von Teilb\*aumen in einer Liste
  854. kann umgekehrt werden. Es werden Prozeduren f\*ur h\*aufig benutzte Traversierungsstrategien
  855. wie
  856. .i "top down"
  857. oder
  858. .i "bottom up"
  859. zur Verf\*ugung gestellt. Ein interaktiver
  860. .i "Graph-Browser"
  861. erlaubt die Inspektion von Graphen in lesbarer Weise und unterst\*utzt so den Programmtest.
  862. .sh 2 Ag
  863. .pp
  864. .i Ag
  865. ist ein Generator f\*ur Attributauswerter
  866. \*([[Gro89c\*(],Gro90\*(]]. Er verarbeitet geordnete
  867. Attributgrammatiken (OAGs)\*([<\*([[Kas80\*(]]\*(>] und sogenannte
  868. .i "higher order"
  869. Attributgrammatiken (HAGs)\*([<\*([[VSK89\*(]]\*(>].
  870. Er basiert auf der abstrakten Syntax oder besser gesagt auf den von
  871. .i Ast
  872. erzeugten Baummodulen. Deshalb ist die Baumstruktur v\*ollig bekannt. Den Terminalen und
  873. Nichtterminalen k\*onnen beliebig viele Attribute zugeordnet werden. Diese werden mit den
  874. Typen der Zielsprache getypt. Dabei sind auch baumwertige Attribute m\*oglich.
  875. .i Ag
  876. erlaubt regellokale Attribute und bietet einen Erweiterungsmechanismus an, welcher einfache
  877. Vererbung f\*ur Attribute und Attributberechnungen zur Verf\*ugung stellt. Dieser gestattet
  878. ebenfalls die Elimination von Kettenregeln. Die Attributberechnungen werden in der
  879. Zielsprache formuliert und sollten in einem funktionalen Stil gehalten sein. Es ist
  880. m\*oglich externe Funktionen von getrennt \*ubersetzten Modulen aufzurufen. Die Verwendung
  881. nicht-funktionaler Anweisungen und von Seiteneffekten ist m\*oglich, verlangt allerdings
  882. sorgf\*altige \*Uberlegung. Die Syntax der Spezifikationssprache ist im Hinblick auf die
  883. Unterst\*utzung kompakter, modularer und lesbarer Dokumente entworfen worden. Eine
  884. Attributgrammatik kann aus mehreren Modulen bestehen, wobei die kontextfreie Grammatik nur
  885. einmal spezifiziert wird.
  886. Es gibt Kurzschreibweisen f\*ur Kopierregeln and gef\*adelte Attribute womit viele triviale
  887. Attribut-Berechnungen weggelassen werden k\*onnen.
  888. Die erzeugten Attributauswerter sind sehr effizient, da sie unter
  889. Verwendung von rekursiven Prozeduren direkt codiert sind.
  890. Die Speicherung der Attribute wird optimiert indem Attribute als
  891. lokale Variable und Prozedurparameter implementiert werden,
  892. wenn ihre Lebenszeit innerhalb eines Besuches liegt.
  893. .sh 2 Estra
  894. .pp
  895. .i Estra
  896. ist ein Generator f\*ur Transformatoren von abstrakten Syntaxb\*aumen\*([<\*([[Vie89\*(]]\*(>].
  897. Die erzeugten Transformations-Module haben als Eingabe einen attributierten Baum und bilden
  898. diesen auf eine Ausgabe beliebiger Art ab. Die Ausgabe kann ein neuer Baum sein, eine lineare
  899. Zwischensprache wie z. B. P-Code, ein Quellprogramm z. B. in Pascal oder eine Folge von
  900. Prozeduraufrufen. In jedem Fall bleibt der Eingabebaum unver\*andert, um das Problem der
  901. Reattributierung aus Konsistenzgr\*unden zu umgehen. Jedoch k\*onnen Teilb\*aume des
  902. Eingabebaums zur Konstruktion eines Ausgabebaums wiederverwendet werden. Die beabsichtigten
  903. Anwendungsgebiete f\*ur die Transformationen sind die Erzeugung von Zwischensprachen aus
  904. abstrakten Syntaxb\*aumen und Optimierer f\*ur interne Baumstrukturen jeden Niveaus.
  905. .i Estra
  906. arbeitet mit dem Werkzeug
  907. .i Ast
  908. zusammen in der Art, da\*s die Eingabeb\*aume mittels von
  909. .i Ast
  910. erzeugten Modulen erstellt werden.
  911. .pp
  912. Die Spezifikation einer Transformation ist regelbasiert. Eine Regel besteht aus einem Muster,
  913. welches ein Baumfragment beschreibt, und einer Aktion. Aktionen bestehen aus Anweisungen der
  914. Zielsprache. Es k\*onnen mehrere Transformationen spezifiziert werden. Die Teilb\*aume eines
  915. Musters k\*onnen in beliebiger Reihenfolge transformiert werden. Sie k\*onnen mehrmals mit
  916. der selben oder mit verschiedenen Transformationen bearbeitet werden. Die Aktionen haben
  917. Lesezugriff auf die Attribute des Eingabebaums. Zus\*atzliche abgeleitete oder vererbte
  918. Attribute k\*onnen w\*ahrend der Transformation berechnet werden. Die Anwendung von Regeln
  919. l\*a\*st sich
  920. durch Bedingungen einschr\*anken. Mehrdeutigkeiten werden mittels Kostenangaben aufgel\*ost.
  921. .pp
  922. Zwei Implementierungen f\*ur den Algorithmus zum Mustervergleich k\*onnen gew\*ahlt werden:
  923. Ein direkt codierter dynamischer Programmierungs-Algorithmus oder ein tabellen-gesteuerter
  924. Baummuster-Vergleicher. In beiden F\*allen besitzt eine Transformation zwei Phasen. W\*ahrend
  925. die Erste die mit minimalen Kosten passenden Muster bestimmt, f\*uhrt die Zweite die
  926. zugeh\*origen Aktionen aus.
  927. .sh 2 Beg
  928. .pp
  929. .i Beg
  930. (\fIb\fPack \fIe\fPnd \fIg\fPenerator) erzeugt Module zur Codeauswahl und zur
  931. Registerzuteilung\*([<\*([[Emm89a\*(],Emm89b\*(]]\*(>].
  932. Codeauswahl wird mittels
  933. Baummuster-Vergleich durchgef\*uhrt. Die Maschinenbefehle werden mit Regeln beschrieben welche
  934. Baummuster enthalten. Der erzeugte Codegenerator hat als Eingabe eine baumf\*ormige
  935. Zwischensprache. Ein Eingabebaum wird abgebildet durch die \*Uberdeckung des Baums mit
  936. Mustern und der anschlie\*senden Ausgabe der zugeh\*origen Maschinenbefehle. Die Regeln sind
  937. mit Kosten versehen, wodurch der Codegenerator eine \*Uberdeckung mit Regeln mit minimalen
  938. Kosten ausw\*ahlen kann.
  939. .pp
  940. Der Benutzer beschreibt auf eventuell mehrdeutige Art und Weise die Abbildung be~stimm~ter
  941. Konstrukte der Zwischensprache. Er braucht keinen Algorithmus zu programmieren, der die beste
  942. Abbildung eines Eingabebaums ausw\*ahlt. Es ist g\*unstig bei der Entwicklung einer
  943. Codegenerator-Beschreibung erst einen Teil der Maschinenbefehle zu spezifizieren, der gro\*s
  944. genug ist, um die ganze Sprache zu \*ubersetzen. Dies f\*uhrt zu einem funktionsf\*ahigen
  945. \*Ubersetzer, welcher eventuell ineffizienten Code erzeugt. Sp\*ater k\*onnen nach und nach
  946. weitere Regeln hinzugef\*ugt werden, was schlie\*slich zu einem \*Ubersetzer f\*uhrt, der
  947. guten Code erzeugt.
  948. .pp
  949. .i Beg
  950. implementiert die Bestimmung einer \*Uberdeckung mit minimalen Kosten unter Verwendung einer
  951. direkt codierten Version des dynamischen Programmierungs-Algorithmus
  952. \*([[Emm88\*(],ESL89\*(]].
  953. .pp
  954. Die Generierung eines Registerzuteilers ist von besonderer Bedeutung, da hier
  955. Handprogrammierung ziemlich schwer und l\*astig ist und weil Fehler in der Registerzuteilung
  956. manchmal schwer zu finden sind. Innerhalb der Regeln k\*onnen die Eigenschaften eines
  957. Maschinenbefehls hinsichtlich der Registerzuteilung spezifiziert werden: die erlaubten
  958. Register f\*ur jeden Operanden, die durch Seiteneffekte ver\*anderten Register und ob es sich
  959. um einen Zweiadre\*sbefehl handelt oder nicht. Zus\*atzlich wird der Registersatz der
  960. Zielmaschine beschrieben. Sogar das Doppelregister-Problem (wie z. B. auf IBM 370) kann
  961. behandelt werden.
  962. .pp
  963. Zwei Arten von Registerzuteilung sind m\*oglich: Die
  964. .i "on the fly"
  965. Registerzuteilung kann nur einfache Registers\*atze behandeln. Sie ist jedoch sehr effizient
  966. und liefert f\*ur viele Maschinen zufriedenstellende Ergebisse. In manchen F\*allen ist der
  967. allgemeine Registerzuteiler n\*otig, welcher eine Art von Vorschau durchf\*uhrt und deshalb
  968. einen zus\*atzlichen Pa\*s ben\*otigt.
  969. .sh 2 Reuse
  970. .pp
  971. .i Reuse
  972. ist eine Bibliothek wiederverwendbarer Module haupts\*achlich f\*ur den Einsatz im
  973. \*Ubersetzerbau\*([<\*([[Gro87b\*(]]\*(>]. Sie enth\*alt Module oder abstrakte Datentypen, die fast
  974. in jedem \*Ubersetzer gebraucht werden:
  975. .ip -
  976. eine dynamische Speicherverwaltung
  977. .ip -
  978. ein Modul f\*ur dynamische und flexible Felder
  979. .ip -
  980. ein Modul zur Speicherung variabel langer Zeichenketten
  981. .ip -
  982. ein Modul zur Zeichenkettenbearbeitung
  983. .ip -
  984. eine Bezeichnertabelle, welche Zeichenketten unter Verwendung eines Hashverfahrens
  985. eindeutig auf ganze Zahlen abbildet
  986. .ip -
  987. Module f\*ur oft verwendete Datenstrukturen wie Mengen von ganzen Zahlen oder bin\*are
  988. Relationen zwischen ganzen Zahlen ohne Beschr\*ankung des Definitionsbereichs.
  989. .sh 1 "Erfahrungen"
  990. .pp
  991. Dieser Abschnitt berichtet \*uber die Erfahrungen des Einsatzes des Werkzeugkastens f\*ur
  992. zwei realistische Anwendungen.
  993. .sh 2 "Modula nach C \*Ubersetzer"
  994. .pp
  995. Die bisher gr\*o\*ste Anwendung des Werkzeugkastens war die Generierung eines Modula-2 nach
  996. C \*Ubersetzers\*([<\*([[Mar90\*(]]\*(>]. Das
  997. .i Mtc
  998. genannte Programm \*ubersetzt Modula-2 Programme in lesbaren C Code ohne Einschr\*ankung
  999. (sogar geschachtelte Prozeduren und Module). Es ist weitgehend automatisch generiert und
  1000. folgt dem in Abschnitt 4 vorgeschlagenen \*Ubersetzer-Modell. Anstelle einer Zwischensprache
  1001. erzeugt
  1002. .i Mtc
  1003. C Code und ben\*otigt deshalb keinen Codegenerator zur Ausgabe von Maschinencode. Es
  1004. enth\*alt so viel von der semantischen Analyse wie f\*ur die Aufgabe gebraucht wird. Die
  1005. semantische Analyse ist ziemlich vollst\*andig und enth\*alt die Behandlung der
  1006. G\*ultigkeitsbereiche, Namensanalyse und Typbestimmung. Es fehlt die \*Uberpr\*ufung von
  1007. Kontextbedingungen, da davon ausgegangen wird, da\*s nur korrekte Programme \*ubersetzt
  1008. werden. Tabelle 1 enth\*alt die Gr\*o\*sen der Spezifikationen und der generierten
  1009. Quell-Module. Der Entwurf und die Implementierung von
  1010. .i Mtc
  1011. wurden im Rahmen einer Diplomarbeit mit einem Aufwand von 6 Mannmonaten durchgef\*uhrt.
  1012. Das Programm ist stabil und hat bereits mehr als 100.000 Zeilen Modula-2 nach C \*ubersetzt.
  1013. .(b L
  1014. .sp 0.5
  1015. .TS
  1016. center box;
  1017. l2 |2 c2 s2 s2 |2 c2 s2 s2 |2 c1 s
  1018. l2 |2 l2 l2 l2 |2 l2 l2 l2 |2 l1 l
  1019. l2 |2 n2 n2 n2 |2 n2 n2 n2 |2 l1 l
  1020. .
  1021. Phase    Spezifikation    Quell-Modul    Werkzeug
  1022. _
  1023.     formal    Code    Summe    Def.    Impl.    Summe    Name    Referenzen
  1024. _
  1025. Lex. Analyse     392    133    525    56    1320    1376    Rex    \*([[Gro87a\*(],Gro88\*(]]
  1026. Zerteiler      951    88    1039    81    3007    3088    Ell    \*([[GrV88\*(],Gro88\*(]]
  1027. Syntaxbaum        189    51    240    579    2992    3571    Ast    \*([[Gro89d\*(]]
  1028. Symboltabelle      115    938    1053    413    1475    1888    Ast    \*([[Gro89d\*(]]
  1029. Sem. Analyse    1886    151    2037    9    3288    3297    Ag    \*([[Gro89c\*(]]
  1030. Codegenerator    2793    969    3762    47    7309    7356    Estra    \*([[Vie89\*(]]
  1031. Wiederverw.    -    -    -    819    2722    3541    Reuse    \*([[Gro87b\*(]]
  1032. Sonstiges    -    -    -    698    3153    3851
  1033. _
  1034. Summe       6326    2330    8656    2702    25266    27968
  1035. .TE
  1036. .sp 0.5
  1037. .ce
  1038. Tabelle 1: Umfang der Spezifikationen und der Quellmodule von \fIMtc
  1039. .)b
  1040. .pp
  1041. Die Gr\*o\*se des Bin\*arprogramms betr\*agt 300 K Bytes.
  1042. Es l\*auft mit einer Geschwindigkeit von 810 Grundsymbolen (\fItokens\fP) pro Sekunde oder
  1043. 167 Zeilen pro Sekunde auf einem SUN/3 Arbeitsplatzrechner (MC 68020 Prozessor). Diese Zahlen
  1044. ber\*ucksichtigen nur die Gr\*o\*se der \*ubersetzten Module. Wenn man zus\*atzlich die
  1045. (transitiv) importierten Definitionsmodule ber\*ucksichtigt, die ebenfalls lexikalisch,
  1046. syntaktisch und semantisch analysiert werden, so erreicht man 1320 Grundsymbole pro Sekunde
  1047. oder 418 Zeilen pro Sekunde. Zum Vergleich die Zahlen f\*ur zwei \*Ubersetzer des
  1048. Rechner-Herstellers: Der C-\*Ubersetzer l\*auft mit einer Geschwindigkeit von
  1049. 97 Zeilen pro Sekunde (ohne \fIHeader\fP-Dateien) bzw. 
  1050. 163 Zeilen pro Sekunde (mit \fIHeader\fP-Dateien) und der Modula-2-\*Ubersetzer mit
  1051. 48 Zeilen pro Sekunde. Die Laufzeit von
  1052. .i Mtc
  1053. ist folgenderma\*sen verteilt:
  1054. .(b
  1055. .TS
  1056. center;
  1057. l l.
  1058. lex. + syn. Analyse + Baumaufbau    42 %
  1059. semantische Analyse    33 %
  1060. C Codegenerierung     25 %
  1061. .TE
  1062. .)b
  1063. Die semantische Analyse verbringt 95% der Zeit mit der Berechnung von Attributen mittels vom
  1064. Benutzer spezifizierten Anweisungen und nur 5% f\*ur die Baumtraversierung bzw. f\*ur
  1065. Besuchs~aktionen. F\*ur 11 Knotentypen sind f\*unf Besuche notwendig.
  1066. .pp
  1067. .i Mtc
  1068. braucht ungef\*ahr 360 K Bytes dynamischen Speicher pro 1000 Quellzeilen zur Speicherung des
  1069. abstrakten Syntaxbaums, der Attribute und der Symboltabelle ohne Optimierung der
  1070. Attributspeicherung. Weitere 600 K Bytes ben\*otigt
  1071. der von 
  1072. .i Estra
  1073. generierte Transformator. Dies ist bei den heutigen Speicherkapazit\*aten ertr\*aglich.
  1074. Es zeigt, da\*s im Gegensatz zu der in der Literatur
  1075. vertretenen Meinung m\*oglich ist, alle Attribute im Baum zu speichern. Wir tun dies sogar
  1076. mit dem sogenannten Umgebungsattribut. Dies wird m\*oglich, indem wir die Symboltabelle als
  1077. abstrakten Datentyp in der Zielsprache programmieren. Die Implementierung ist zeit- und
  1078. speichereffizient durch die Ausnutzung von Zeigersemantik und
  1079. .i "structure sharing" .
  1080. .sh 2 "Codegenerator f\*ur Modula-2-\*Ubersetzer"
  1081. .pp
  1082. In einer anderen Anwendung wurde der urspr\*unglich handgeschriebene Codegenerator des
  1083. GMD Modula-2-\*Ubersetzers
  1084. .i Mocka
  1085. durch zwei mit
  1086. .i Beg
  1087. erzeugte Versionen ersetzt. Die Zielmaschine war ein MC 68020 Prozessor. Die Spezifikation
  1088. des Codegenerators umfa\*st 1625 Zeilen und enth\*alt 187 Regeln und 99
  1089. Zwischensprach-Operatoren. Zum Vergleich der Qualit\*at des erzeugten Maschinencodes haben
  1090. wir die Laufzeiten f\*ur eine Sammlung von Benchmark-Programmen gemessen (siehe Tabelle 2).
  1091. .(z
  1092. .sz -2
  1093. .TS
  1094. center box tab(;);
  1095. l || c | c | c | c | c | c | c | c | c | c || c.
  1096.  ;Perm;Towers;Queens;Intmm;Mm;Puzzle;Quick;Tree;Bubble;FFT;Summe
  1097. _
  1098. Mocka ;40;58;37;53;103;285;32;72;56;152;888
  1099. Begra ;42;57;35;54;104;297;32;58;56;153;888
  1100. Begfly;42;57;34;54;102;299;33;56;56;151;884
  1101. Sun   ;67;90;28;83;101;263;41;81;63;150;967
  1102. .TE
  1103. .sz +2
  1104. .sp
  1105. .ce
  1106. Tabelle 2: Vergleich der Codequalit\*at (Laufzeiten in \fIticks\fP = 1/60 Sek.)
  1107. .)z
  1108. Dabei ist
  1109. .i Mocka
  1110. der GMD Modula-2-\*Ubersetzer mit handgeschriebenem Codegenerator,
  1111. .i Begra
  1112. und
  1113. .i Begfly
  1114. sind die mit
  1115. .i Beg
  1116. erzeugten Versionen mit dem allgemeinen bzw. mit dem
  1117. .i "on the fly"
  1118. Registerzuteiler, und
  1119. .i Sun
  1120. der SUN Modula-2-\*Ubersetzer Version 1.0. Im Durchschnitt ist der Code von mit
  1121. .i Beg
  1122. erzeugten Codegeneratoren genau so gut, wie der des handgeschriebenen Codegenerators.
  1123. .(z
  1124. .TS
  1125. center box tab(;);
  1126. l | n.
  1127. Mocka ;2.9
  1128. Begfly;3.2
  1129. Begra ;3.9
  1130. Sun   ;25.4
  1131. .TE
  1132. .sp
  1133. .ce
  1134. Tabelle 3: Vergleich der \*Ubersetzungszeiten (in Sek.)
  1135. .)z
  1136. .pp
  1137. Tabelle 3 vergleicht die \*Ubersetzungszeiten f\*ur ein 1116 Zeilen langes Programm. Alle
  1138. Messungen wurden auf einer SUN 3/60 durchgef\*uhrt, die gemessenen Zeiten waren
  1139. .i "user"
  1140. Zeiten. Die Gr\*o\*se des Codegenerators nahm von 5140 Zeilen (17,117 Grundsymbole) f\*ur
  1141. die handgeschriebene Version auf 9574 Zeilen (27,044 Grundsymbole) zu.
  1142. .sh 1 "Zusammenfassung und Ausblick"
  1143. .pp
  1144. Wir haben einen Werkzeugkasten mit \*Ubersetzerbau-Werkzeugen vorgestellt, womit sich
  1145. \*Ubersetzer f\*ur Programmiersprachen weitgehend automatisch generieren lassen.
  1146. Die \*Ubersetzerbau-Werkzeuge unterst\*utzen die Konstruktion nahezu aller \*Ubersetzerphasen.
  1147. Die Werkzeuge sind sehr m\*achtig, flexibel und weitgehend unabh\*angig von einander.
  1148. Besonders hervorzuheben sind die praktische Brauchbarkeit der Werkzeuge, der deutlich
  1149. reduzierte Erstellungsaufwand f\*ur \*Ubersetzer und die hohe Qualit\*at der generierten
  1150. \*Ubersetzer.
  1151. Von der Effizienz her sind die Werkzeuge konkurrenzf\*ahig zur Programmierung von Hand.
  1152. Sie unterst\*utzen einen breiten Bereich von \*Ubersetzerstrukturen und erlauben die
  1153. Konstruktion von \*Ubersetzern mit Produktionsqualit\*at.
  1154. Erste realistische Anwendungen zeigen die ausgezeichnete Leistungsf\*ahigkeit der Werkzeuge.
  1155. .pp
  1156. Die \*Ubersetzerbau-Werkzeuge eignen sich f\*ur viele Aufgabenstellungen, die \*uber die
  1157. Konstruktion von reinen \*Ubersetzern hinausgehen. Sie gestatten beispielsweise die
  1158. Implementierung von Pr\*aprozessoren, die Spracherweiterungen und Sprachdialekte auf
  1159. Standardsprachen abbilden. Wie eines unserer Anwendungsbeispiele zeigte, lassen sich Umsetzer
  1160. von einer Quellsprache in eine andere erstellen. Weiterhin ist etwa die Generierung von
  1161. Pr\*ufprogrammen f\*ur Programmierkonventionen m\*oglich.
  1162. .pp
  1163. Die Optimierung der Attributspeicherung des Werkzeugs
  1164. .i Ag
  1165. werden wir verbessern, damit Attribute
  1166. gegebenenfalls auch als globale Variable und globale Keller implementiert werden k\*onnen.
  1167. Au\*serdem sollte die Transformation von Grammatiken, die nicht die
  1168. OAG-Eigenschaft besitzen, in OAG-Grammatiken automatisiert werden.
  1169. .pp
  1170. F\*ur das Werkzeug
  1171. .i Estra
  1172. ist ein Redesign geplant. Die Spezifikationssprache l\*a\*st sich vereinfachen, und die
  1173. Integration des Werkzeug mit
  1174. .i Ast
  1175. kann verbessert werden. Die Effizienz der ge~ne~rier~ten Transformations-Module l\*a\*st sich
  1176. sowohl hin~sicht~lich Laufzeit als auch hinsichtlich Speicherverbrauch verbessern.
  1177. .pp
  1178. Die Optimierungsphase eines \*Ubersetzers sollte selbstverst\*andlich auch unterst\*utzt
  1179. werden. Dies kann entweder durch einen wiederverwendbaren sprachunabh\*angigen Optimierer,
  1180. durch einen parameterisierbaren Optimierer oder durch einen Optimierergenerator geschehen.
  1181. .pp
  1182. Das Werkzeug
  1183. .i Beg
  1184. wird in folgende Richtungen erweitert werden: Generierung eines globalen Registerzuteilers,
  1185. Unterst\*utzung der Befehlsumordnung (\fIinstruction scheduling\fP) und einer Einrichtung
  1186. zur direkten Generierung von bin\*arem Objektcode.
  1187. .uh Danksagung
  1188. .pp
  1189. Wir danken allen die zur Entstehung des Werkeugkastens und dieses Aufsatzes durch aktive
  1190. Mitarbeit oder durch ihre Ideen beigetragen haben:
  1191. Michael Besser,
  1192. Carsten Gerlhof,
  1193. Bob Gray,
  1194. Eduard Klein,
  1195. Rudolf Landwehr,
  1196. Matthias Martin,
  1197. Thomas M\*uller,
  1198. F. W. Schr\*oer,
  1199. Dirk Schwartz-Hertzner,
  1200. Doris Vielsack,
  1201. Bertram Vielsack und
  1202. William M. Waite.
  1203. .fi
  1204. .sz 12
  1205. .[]
  1206. .[-
  1207. .ds [F ASU86
  1208. .ds [A A\*(p]\*(a]V\*(p] Aho
  1209. .as [A \*(c]R\*(p] Sethi
  1210. .as [A \*(m]J\*(p]\*(a]D\*(p] Ullman
  1211. .ds [T Compilers: Principles, Techniques, and Tools
  1212. .ds [I Addison Wesley
  1213. .ds [C Reading, M\&A
  1214. .ds [D 1986
  1215. .][
  1216. .[-
  1217. .ds [F DeP82
  1218. .ds [A F\*(p] DeRemer
  1219. .as [A \*(n]T\*(p] Pennello
  1220. .ds [T Efficient Computation of LALR(1) Look-Ahead Sets
  1221. .nr [P 1
  1222. .ds [P 615-649
  1223. .ds [J ACM Trans. Prog. Lang. and Systems
  1224. .ds [V 4
  1225. .ds [N 4
  1226. .ds [D Oct. 1982
  1227. .][
  1228. .[-
  1229. .ds [F Emm88
  1230. .ds [A H\*(p] Emmelmann
  1231. .ds [T Automatische Erzeugung effizienter Codegeneratoren
  1232. .ds [R Diplomarbeit
  1233. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1234. .ds [D Sep. 1988
  1235. .][
  1236. .[-
  1237. .ds [F ESL89
  1238. .ds [A H\*(p] Emmelmann
  1239. .as [A \*(c]F\*(p]\*(a]W\*(p] Schr\\*:oer
  1240. .as [A \*(m]R\*(p] Landwehr
  1241. .ds [T BEG - a Generator for Efficient Back Ends
  1242. .ds [J SI\&GPLAN Notices
  1243. .ds [V 24
  1244. .ds [N 7
  1245. .nr [P 1
  1246. .ds [P 227-237
  1247. .ds [D July 1989
  1248. .][
  1249. .[-
  1250. .ds [F Emm89a
  1251. .ds [A H\*(p] Emmelmann
  1252. .ds [T Automatische Erzeugung effizienter Codegeneratoren
  1253. .ds [R GMD-Studie Nr. 158
  1254. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1255. .ds [D 1989
  1256. .][
  1257. .[-
  1258. .ds [F Emm89b
  1259. .ds [A H\*(p] Emmelmann
  1260. .ds [T BEG - A Back End Generator - User Manual
  1261. .ds [R Arbeitspapier Nr. 420
  1262. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1263. .ds [D Dec. 1989
  1264. .][
  1265. .[-
  1266. .ds [F Gro87a
  1267. .ds [A J\*(p] Grosch
  1268. .ds [T Rex - A Scanner Generator
  1269. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1270. .ds [R Compiler Generation Report No. 5
  1271. .ds [N 5
  1272. .ds [D Dec. 1987
  1273. .][
  1274. .[-
  1275. .ds [F Gro87b
  1276. .ds [A J\*(p] Grosch
  1277. .ds [T Reusable Software - A Collection of Modula-Modules
  1278. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1279. .ds [R Compiler Generation Report No. 4
  1280. .ds [N 4
  1281. .ds [D Sep. 1987
  1282. .][
  1283. .[-
  1284. .ds [F GrV88
  1285. .ds [A J\*(p] Grosch
  1286. .as [A \*(n]B\*(p] Vielsack
  1287. .ds [T The Parser Generators Lalr and Ell
  1288. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1289. .ds [R Compiler Generation Report No. 8
  1290. .ds [N 8
  1291. .ds [D Apr. 1988
  1292. .][
  1293. .[-
  1294. .ds [F Gro88
  1295. .ds [A J\*(p] Grosch
  1296. .ds [T Generators for High-Speed Front-Ends
  1297. .ds [V 371
  1298. .ds [J LNCS
  1299. .ds [C Berlin
  1300. .ds [I Springer Verlag
  1301. .nr [P 1
  1302. .ds [P 81-92
  1303. .ds [D Oct. 1988
  1304. .][
  1305. .[-
  1306. .ds [F Gro89a
  1307. .ds [A J\*(p] Grosch
  1308. .ds [T Efficient Generation of Lexical Analysers
  1309. .ds [J Software\(emPractice & Experience
  1310. .ds [V 19
  1311. .ds [N 11
  1312. .nr [P 1
  1313. .ds [P 1089-1103
  1314. .ds [D Nov. 1989
  1315. .][
  1316. .[-
  1317. .ds [F Gro89b
  1318. .ds [A J\*(p] Grosch
  1319. .ds [T Efficient and Comfortable Error Recovery in Recursive Descent Parsers
  1320. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1321. .ds [R Compiler Generation Report No. 19
  1322. .ds [N 19
  1323. .ds [D Dec. 1989
  1324. .][
  1325. .[-
  1326. .ds [F Gro89c
  1327. .ds [A J\*(p] Grosch
  1328. .ds [T Ag - An Attribute Evaluator Generator
  1329. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1330. .ds [R Compiler Generation Report No. 16
  1331. .ds [N 16
  1332. .ds [D Aug. 1989
  1333. .][
  1334. .[-
  1335. .ds [F Gro89d
  1336. .ds [A J\*(p] Grosch
  1337. .ds [T Ast - A Generator for Abstract Syntax Trees (Revised Version)
  1338. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1339. .ds [R Compiler Generation Report No. 15
  1340. .ds [N 15
  1341. .ds [D Aug. 1989
  1342. .][
  1343. .[-
  1344. .ds [F Gro89e
  1345. .ds [A J\*(p] Grosch
  1346. .ds [T Tool Support for Data Structures
  1347. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1348. .ds [R Compiler Generation Report No. 17
  1349. .ds [N 17
  1350. .ds [D Nov. 1989
  1351. .][
  1352. .[-
  1353. .ds [F Gro90
  1354. .ds [A J\*(p] Grosch
  1355. .ds [T Object-Oriented Attribute Grammars
  1356. .ds [E A\*(p]\*(a]E\*(p] Harmanci
  1357. .as [E \*(n]E\*(p] Gelenbe
  1358. .nr [E 2
  1359. .ds [B Proceedings of the Fifth International Symposium on Computer and Information Sciences (ISCIS V)
  1360. .ds [C Cappadocia, Nevsehir, Turkey
  1361. .nr [P 1
  1362. .ds [P 807-816
  1363. .ds [D Oct. 1990
  1364. .][
  1365. .[-
  1366. .ds [F Joh75
  1367. .ds [A S\*(p]\*(a]C\*(p] Johnson
  1368. .ds [T Yacc \(em  Yet Another Compiler-Compiler
  1369. .ds [R Computer Science Technical Report 32
  1370. .ds [I Bell Telephone Laboratories
  1371. .ds [C Murray Hill, NJ
  1372. .ds [D July 1975
  1373. .][
  1374. .[-
  1375. .ds [F Kas80
  1376. .ds [A U\*(p] Kastens
  1377. .ds [T Ordered Attribute Grammars
  1378. .nr [P 1
  1379. .ds [P 229-256
  1380. .ds [J Acta Inf.
  1381. .ds [V 13
  1382. .ds [D 1980
  1383. .ds [N 3
  1384. .][
  1385. .[-
  1386. .ds [F Les75
  1387. .ds [A M\*(p]\*(a]E\*(p] Lesk
  1388. .ds [T LEX \(em A Lexical Analyzer Generator
  1389. .ds [R Computing Science Technical Report 39
  1390. .ds [I Bell Telephone Laboratories
  1391. .ds [C Murray Hill, NJ
  1392. .ds [D 1975
  1393. .][
  1394. .[-
  1395. .ds [F Mar90
  1396. .ds [A M\*(p] Martin
  1397. .ds [T Entwurf und Implementierung eines \\*:Ubersetzers von Modula-2 nach C
  1398. .ds [R Diplomarbeit
  1399. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1400. .ds [D Feb. 1990
  1401. .][
  1402. .[-
  1403. .ds [F R\*oh76
  1404. .ds [A J\*(p] R\\*:ohrich
  1405. .ds [T Syntax-Error Recovery in LR-Parsers
  1406. .ds [E H\*(p] Schneider
  1407. .ds [E H.-J\*(p] Schneider
  1408. .as [E \*(n]M\*(p] Nagl
  1409. .nr [E 2
  1410. .ds [S Programmiersprachen, 4. Fachtagung der GI, Erlangen
  1411. .ds [B Informatik-Fachberichte
  1412. .ds [V 1
  1413. .nr [P 1
  1414. .ds [P 175-184
  1415. .ds [C Berlin
  1416. .ds [I Springer Verlag
  1417. .ds [D 1976
  1418. .][
  1419. .[-
  1420. .ds [F R\*oh80
  1421. .ds [A J\*(p] R\\*:ohrich
  1422. .ds [T Methods for the Automatic Construction of Error Correcting Parsers
  1423. .ds [J Acta Inf.
  1424. .ds [V 13
  1425. .ds [N 2
  1426. .nr [P 1
  1427. .ds [P 115-139
  1428. .ds [D 1980
  1429. .][
  1430. .[-
  1431. .ds [F R\*oh82
  1432. .ds [A J\*(p] R\\*:ohrich
  1433. .ds [T Behandlung syntaktischer Fehler
  1434. .ds [J Informatik Spektrum
  1435. .ds [V 5
  1436. .ds [N 3
  1437. .nr [P 1
  1438. .ds [P 171-184
  1439. .ds [D 1982
  1440. .][
  1441. .[-
  1442. .ds [F Vie89
  1443. .ds [A B\*(p] Vielsack
  1444. .ds [T Spezifikation und Implementierung der Transformation attributierter B\\*:aume
  1445. .ds [R Diplomarbeit
  1446. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1447. .ds [D June 1989
  1448. .][
  1449. .[-
  1450. .ds [F VSK89
  1451. .ds [A H\*(p]\*(a]H\*(p] Vogt
  1452. .as [A \*(c]S\*(p]\*(a]D\*(p] Swierstra
  1453. .as [A \*(m]M\*(p]\*(a]F\*(p] Kuiper
  1454. .ds [T Higher Order Attribute Grammars
  1455. .ds [J SI\&GPLAN Notices
  1456. .ds [V 24
  1457. .ds [N 7
  1458. .nr [P 1
  1459. .ds [P 131-145
  1460. .ds [D July 1989
  1461. .][
  1462. .bp 1
  1463. .lp
  1464. .b Inhalt
  1465. .sp
  1466. .xp
  1467.